import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1、构建并存储图、初始化入度数组
        int[] in = new int[numCourses]; // 记录每个顶点的入度
        Map<Integer, List<Integer>> edges = new HashMap<>(); // 邻接表(记录顶点的出边)
        for (int[] arr : prerequisites) {
            int a = arr[0], b = arr[1]; // b -> a
            if (!edges.containsKey(b)) {
                edges.put(b, new ArrayList<>());
            }
            edges.get(b).add(a); // b -> a
            in[a]++; // a的入度+1
        }
        // 2、对图进行拓扑排序
        // (1)将所有入度为0的点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) { // i这个点的入度为0
                queue.offer(i); // 将i加入到队列中
            }
        }
        // (2)BFS
        while (!queue.isEmpty()) {
            int x = queue.poll();
            // 将x的出边全部删除
            // 可能该顶点并没有出边，也就意味着Map中并未初始化，得预防这种情况
            List<Integer> list = edges.getOrDefault(x, null);
            if (list != null) {
                for (int t : list) {
                    if (--in[t] == 0) { // 如果删除之后，入度为0，则加入队列
                        queue.offer(t);
                    }
                }
            }
        }
        // (3)判断图中是否还有顶点（判断入度数组是否还有值）
        for (int x : in) {
            if (x != 0) { // 说明还有顶点的入度不为0，则图中还有顶点
                return false;
            }
        }
        return true;
    }
}